迷宫生成算法总结 |
您所在的位置：网站首页 › 生成迷宫算法 知乎 › 迷宫生成算法总结 |
迷宫生成算法总结
|
最近闲来无事想做一个质量高一点的进阶版的迷宫小游戏，首先就要先生成最基础的迷宫地图，因此学习并整理了一下迷宫生成算法。由于python更容易实现这些算法，因此首先使用pyhon将各种生成算法整理一遍，之后再用Qt或者javascript重写一遍，再加上可视化。 目前已经使用python实现了一个简单的可玩版本，可在迷宫游戏python实现查看。 大概了解了一下，生成迷宫的算法主要有三种思路，其中最小生成树算法又可以分为选点法（prim）和选边法（kruskal）： 随机深度优先算法递归分割算法(TODO)随机prim最小生成树算法*kruskal最小生成树算法（使用并查集实现）❓ BrainStorm：能否编程生成圆形的迷宫？如下图所示，如果有读者有思路，欢迎留言讨论。 话不多说，进入正文。 1 随机深度优先算法之所以叫做随机深度优先算法，是因为传统的深度优先算法中已经确定了遍历上下左右四个方向的顺序，因此每次生成的地图都是一样的，而且特别简单。为了增加地图的随机性，需要在每次遍历上下左右四个方向的时候先将四个方向随机打乱再进行遍历。先看看随机深度优先算法生成的地图，如果dfs起点随机选择（我这选择的是终点旁边的点作为dfs的起点）效果还是不错的，结果如下图： 
python3的源代码为： import numpy as np import time import random import copy class Maze(object): def __init__(self, width = 11, height = 11): # 迷宫最小长宽为5 assert width >= 5 and height >= 5, "Length of width or height must be larger than 5." # 确保迷宫的长和宽均为奇数 self.width = (width // 2) * 2 + 1 self.height = (height // 2) * 2 + 1 self.start = [1, 0] self.destination = [self.height - 2, self.width - 1] self.matrix = None def print_matrix(self): for i in range(self.height): for j in range(self.width): if self.matrix[i][j] == -1: print('□', end = '') elif self.matrix[i][j] == 0: print(' ', end = '') elif self.matrix[i][j] == 1: print('■', end = '') print('') def generate_matrix_dfs(self): # 地图初始化，并将出口和入口处的值设置为0 self.matrix = -np.ones((self.height, self.width)) self.matrix[self.start[0], self.start[1]] = 0 self.matrix[self.destination[0], self.destination[1]] = 0 visit_flag = [[0 for i in range(self.width)] for j in range(self.height)] def check(row, col, row_, col_): temp_sum = 0 for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]: temp_sum += self.matrix[row_ + d[0]][col_ + d[1]] return temp_sum 0 and row_ 0 and col_ = 5 and height >= 5, "Length of width or height must be larger than 5." self.width = (width // 2) * 2 + 1 self.height = (height // 2) * 2 + 1 self.start = [1, 0] self.destination = [self.height - 2, self.width - 1] self.matrix = None def print_matrix(self): for i in range(self.height): for j in range(self.width): if self.matrix[i][j] == -1: print('□', end = '') elif self.matrix[i][j] == 0: print(' ', end = '') elif self.matrix[i][j] == 1: print('■', end = '') print('') # 虽然说是prim算法，但是我感觉更像随机广度优先算法 def generate_matrix_prim(self): # 地图初始化，并将出口和入口处的值设置为0 self.matrix = -np.ones((self.height, self.width)) def check(row, col): temp_sum = 0 for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]: temp_sum += self.matrix[row + d[0]][col + d[1]] return temp_sum 0 and row_ 0 and col_ = 5 and height >= 5, "Length of width or height must be larger than 5." self.width = (width // 2) * 2 + 1 self.height = (height // 2) * 2 + 1 self.start = [1, 0] self.destination = [self.height - 2, self.width - 1] self.matrix = None def print_matrix(self): for i in range(self.height): for j in range(self.width): if self.matrix[i][j] == -1: print('□', end = '') elif self.matrix[i][j] == 0: print(' ', end = '') elif self.matrix[i][j] == 1: print('■', end = '') print('') # 最小生成树算法-kruskal（选边法）思想生成迷宫地图，这种实现方法最复杂。 def generate_matrix_kruskal(self): # 地图初始化，并将出口和入口处的值设置为0 self.matrix = -np.ones((self.height, self.width)) def check(row, col): ans, counter = [], 0 for d in [[0, 1], [0, -1], [1, 0], [-1, 0]]: row_, col_ = row + d[0], col + d[1] if row_ > 0 and row_ 0 and col_ |
在这里总结几个我在编程实现的过程中遇到的小问题：【本文地址】